<HTML>
<head>
<title>An example of coloring with precolored nodes</title>
</head>
<body bgcolor="#FFFFFF">
<h2>Graph coloring with precolored nodes</h2>
&#169;1997 by <a href="http://www.cs.princeton.edu/~appel">Andrew W. Appel</a><br>

<h3>Supplement to the books,</h3>

<a href="https://www.cs.princeton.edu/~appel/modern/basic/ml"><img alt="Modern Compiler Implementation in ML" src="https://www.cs.princeton.edu/~appel/modern/basic/ml/cover35.gif"></a>
<a href="https://www.cs.princeton.edu/~appel/modern/basic/c"><img alt="Modern Compiler Implementation in C" src="https://www.cs.princeton.edu/~appel/modern/basic/c/cover35.gif"></a>
<a href="https://www.cs.princeton.edu/~appel/modern/basic/java"><img alt="Modern Compiler Implementation in Java" src="https://www.cs.princeton.edu/~appel/modern/basic/java/cover35.gif"></a>

<p>
This page explains register allocation using 
<a href="http://www.cs.princeton.edu/~appel/papers/coalesce.ps">Iterated Register Coalescing</a>
in the presence of precolored nodes (temporary variables already assigned to machine registers).

<p>
The instruction-selection phase of a compiler may generate
arbitrarily many temporary variables, which must then
be assigned to a finite set of machine registers.
<p>
But some of the variables produced by instruction
selection must be assigned to specific machine registers,
because of standard parameter-passing conventions,
or the use of special registers such as stack pointer or
frame pointer.  These variables are <i>precolored</i>
before register allocation.  For each machine register,
there may be at most one node precolored with that color.

<p>
Precolored nodes should be considered to have infinite degree.
Therefore,  <i>simplify</i>, <i>freeze</i>, and <i>spill</i> cannot
be performed on them.  However, an ordinary (non-precolored) node may be
coalesced with a precolored node.  

<h4>Example</h4>

Consider the following program, produced by the instruction-selection
phase of a compiler:

<pre>
enter:
  c := r3
  a := r1
  b := r2
  d := 0
  e := a
loop:
  d := d+b
  e := e-1
  if e>0 goto loop
  r1 := d
  r3 := c
  return
    [ r1,r3 live out]
</pre>

The target machine has three registers, <b>r1</b>, <b>r2</b>, 
<b>r3</b>.  Registers <b>r1</b> and <b>r2</b> are caller-save,
and <b>r3</b> is callee-save.  The code generator has
therefore made arrangements to preserve the value of <b>r3</b>
explicitly, by copying it into the temporary <b>c</b> and back again.

The interference graph for this function is:

<p><img src="color1a.gif"><p>

The register allocation proceeds as follows (with <i>K</i>=3):
<ol>
<li>In this graph, there is no opportunity for <b>simplify</b> or
<b>freeze</b> (because all the non-precolored nodes have degree greater
than <i>K</i>).  Any attempt to <b>coalesce</b> will produce a
coalesced node adjacent to <i>K</i> or more high-degree nodes.  Therefore
we must <b>spill</b> some node.  We calculate spill priorities as
follows:
<table>
<tr><td>Node</td>
<td></td>
<td><table><tr><td>uses+defs</td></tr><tr><td>outside loop</td></tr></table></td>
<td></td>
<td><table><tr><td>uses+defs</td></tr><tr><td>within loop</td></tr></table></td>
<td></td>
<td>degree</td>
<td></td>
<td><table><tr><td>spill</td></tr><tr><td>priority</td></tr></table></td>
</tr>

<tr><td><b>a:</b></td><td>(</td><td align=center>2</td><td>+10*</td><td align=center>0</td><td>) /</td><td align=center>4</td><td>=</td><td align=center>0.50</td></tr>
<tr><td><b>b:</b></td><td>(</td><td align=center>1</td><td>+10*</td><td align=center>1</td><td>) /</td><td align=center>4</td><td>=</td><td align=center>2.75</td></tr>
<tr><td><b>c:</b></td><td>(</td><td align=center>2</td><td>+10*</td><td align=center>0</td><td>) /</td><td align=center>6</td><td>=</td><td align=center>0.33</td></tr>
<tr><td><b>d:</b></td><td>(</td><td align=center>2</td><td>+10*</td><td align=center>2</td><td>) /</td><td align=center>4</td><td>=</td><td align=center>5.50</td></tr>
<tr><td><b>e:</b></td><td>(</td><td align=center>1</td><td>+10*</td><td align=center>3</td><td>) /</td><td align=center>3</td><td>=</td><td align=center>10.3</td></tr>
</table>
Node <b>c</b> has the lowest priority--it inteferes with many other temporaries but is rarely used--so
it should be spilled first. 
<p>
Spilling <b>c</b>, we obtain the graph,

<p><img src="color1b.gif"><p>

<li>We can now coalesce <b>a</b> and <b>e</b>, since the resulting node
will be adjacent to fewer than <i>K</i> high-degree nodes (after coalescing,
node <b>d</b> will be low-degree, though it is high-degree right now).
No other <b>simplify</b> or <b>coalesce</b> is possible now.
Coalescing <b>a+e</b> gives,

<p><img src="color1c.gif"><p>

<li>Now we could coalesce <b>ae+r1</b> or coalesce <b>b+r2</b>.  Let us do the latter:

<p><img src="color1d.gif"><p>

<li>We can now coalesce either <b>ae+r1</b> or coalesce <b>d+r1</b>.  Let us do the former:

<p><img src="color1e.gif"><p>

<li>We cannot now coalesce <b>r1ae+d</b> because the move is <i>constrained:</i>
the nodes <b>r1ae</b> and <b>d</b> interfere.  We must <b>simplify</b> <b>d</b>:

<p><img src="color1f.gif"><p>

<li>Now we have reached a graph with only precolored nodes, so we pop nodes from the
stack and assign colors to them.  First we pick <b>d</b>, which can be assigned
color <b>r3</b>.  Nodes <b>a</b>, <b>b</b>, <b>e</b> have already been assigned
colors by coalescing.  But node <b>c</b>, which was a <i>potential spill</i>, turns into
an <i>actual spill</i> when it is popped from the stack, since no color can be found for it.

<li>Since there was spilling in this round, we must rewrite the program 
to include spill instructions.  For each use (or definition) of <b>c</b>, we
make up a new temporary, and fetch (or store) it immediately afterward (or beforehand):

<pre>
enter:
  c1 := r3
  M[c_loc] := c1
  a := r1
  b := r2
  d := 0
  e := a
loop:
  d := d+b
  e := e-1
  if e>0 goto loop
  r1 := d
  c2 := M[c_loc]
  r3 := c2
  return
    [ r1,r3 live out]
</pre>

<li>Now we build a new inteference graph:

<p><img src="color1g.gif"><p>

<li>Graph coloring proceeds as follows.  We can immediately coalesce <b>c1+r3</b>
and then <b>c2+r3</b>:

<p><img src="color1h.gif"><p>

<li>Then, as before, we can coalesce <b>a+e</b> and then <b>b+r2</b>:

<p><img src="color1i.gif"><p>

<li>As before, we can coalesce <b>ae+r1</b> and then simplify <b>d</b>:

<p><img src="color1j.gif"><p>

<li>Now we start popping from the stack: we select color <b>r3</b> for <b>d</b>,
and this was the only node on the stack--all other nodes were coalesced or precolored.
So the coloring is:

<table>
<tr><td>Node</td><td>Color</td></tr>
<tr><td align=center>a</td><td align=center>r1</td></tr>
<tr><td align=center>b</td><td align=center>r2</td></tr>
<tr><td align=center>c</td><td align=center>r3</td></tr>
<tr><td align=center>d</td><td align=center>r3</td></tr>
<tr><td align=center>e</td><td align=center>r1</td></tr>
</table>

<li>Now we can rewrite the program with this register assignment:

<pre>
enter:
  r3 := r3
  M[c_loc] := r3
  r1 := r1
  r2 := r2
  r3 := 0
  r1 := r1
loop:
  r2 := r3+r2
  r1 := r1-1
  if r1>0 goto loop
  r1 := r3
  r3 := M[c_loc]
  r3 := r3
  return
    [ r1,r3 live out]
</pre>

<li>Finally, we can delete any move instruction whose source and
destination are the same; these are the result of coalescing:

<pre>
enter:
  M[c_loc] := r3
  r3 := 0
loop:
  r2 := r3+r2
  r1 := r1-1
  if r1>0 goto loop
  r1 := r3
  r3 := M[c_loc]
  return
    [ r1,r3 live out]
</pre>

The final program has only one uncoalesced move instruction.


</body>
</html>
